package com.tgy.cmp;


import com.tgy.Sort;

import java.util.Objects;

/**
 * @Author: tgy
 * @Date: 2020-10-15 09:17
 */
public class MergeSort<E> extends Sort<E> {

    private E[] transition;



    @Override
    protected void sort() {

        if (Objects.isNull(transition)) {
            transition = (E[]) new Object[elements.length >> 1];
        }

        if (elements.length <= 1) {
            return;
        }

        divide(0,elements.length);
    }

    /**
     * divide array
     * @param begin element
     * @param end element
     */
    private void divide(int begin,int end) {

//       divide to remain one or zero element
        if (end - begin < 2) {

            return;
        }

        int mid = (begin + end) >> 1;

        divide(begin,mid);
        divide(mid,end);

        merge(begin, mid, end);
    }

    /**
     * merge [begin, mid) and [mid, end)
     * @param begin element
     * @param mid element
     * @param end element
     */
    private void merge(int begin,int mid, int end) {

        int lb = 0, ll = mid - begin;
        int rb = mid, ai = begin;

        for (int i = 0; i < ll; i++) {

            transition[i] = elements[begin + i];
        }

         while (lb < ll){

//            <= 排序就是稳定排序
            if (rb >= end || compare(transition[lb],elements[rb]) <= 0) {

                elements[ai++] = transition[lb++];

            }else {

                elements[ai++] = elements[rb++];
            }
        }

    }
}
